package tulingxueyuan117;

import java.util.Arrays;

/**
 * Author: Zhang Dongwei
 * Date: 2022/11/24 20:38
 * 给你一个整数 n ，对于 0 <= i <= n 中的每个 i ，计算其二进制表示中 1 的个数 ，返回一个长度为 n + 1 的数组 ans 作为答案。
 */
public class p50_比特位计数_338 {
    public static void main(String[] args) {
        int n = 5;
        System.out.println(4/2);
        int [] res = new int[n+1];
        res = countBits(n);
        System.out.println(Arrays.toString(res));
    }


//    public static int[] countBits(int n) {
//        int [] res = new int[n+1];
//        for (int i = 1; i <= n; i++){
//            res[i] = res[i&(i-1)]+1;
//        }
//        return res;
//    }

//    运用奇偶性
    public static int[] countBits(int n) {
        int[] res = new int[n+1];
        res[0] = 0;
        for (int i = 1; i <= n; i++){
            if(i%2==0){
                res[i] = res[i/2];
            }else {
                res[i] = res[i-1] + 1;
            }
        }
        return res;
    }
}
